package com.njupt.HuiSu;

import java.util.ArrayList;
import java.util.List;

public class SolveNQueens1 {

    public List<List<String>> solveNQueens(int n) {

        int[] location = new int[n];
        List<List<String>> results = new ArrayList<>();
        nQueens1(0,n,location,results);
        return results;
    }

    public void nQueens1(int k,int n,int[] location,List<List<String>> results){
        //遍历每一行n个棋盘格子
        for (int i = 0; i <n ; i++) {
            //第k个皇后能够放入第i个棋盘格子
            if(isLocation(k,i,location)){
                location[k] = i;
                if(k == n-1){
                    //strBs.clear();
                    List<String> strBs = new ArrayList<>();
                    for (int j = 0; j < location.length; j++) {
                        String str = "";
                        for (int l = 0; l < n; l++) {
                            str +='.';
                        }
                        StringBuffer strTemp = new StringBuffer(str);
                        strTemp.setCharAt(location[j],'Q');
                        strBs.add(strTemp.toString());
                    }
                    System.out.println();
                    results.add(strBs);
                }else {
                    nQueens1(k+1,n,location,results);
                }
            }
        }
    }




    public boolean isLocation(int k,int i,int[] location){
        for (int j = 0; j < k; j++) {
            if(location[j]==i || Math.abs(location[j]-i) == Math.abs(k-j)){
                return false;
            }
        }
        return true;
    }




    public static void main(String[] args) {
        SolveNQueens1 test = new SolveNQueens1();
//        test.nQueens(0, test.n, test.location);
        List<List<String>> lists = test.solveNQueens(4);
        System.out.println(lists);

//        ArrayList<List<String>> results = new ArrayList<>();
//        List<String> strings = new ArrayList<>();
//        strings.add("wjm");
//        strings.add("xfy");
//        strings.add("wzx");
//        System.out.println(strings);
//
//        results.add(strings);
//        System.out.println(results);
//        strings.remove(1);
//        System.out.println(strings);
//        System.out.println(results);

    }
}
